package com.wlr.study.task;

import java.util.*;

public class Game {
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static class Coordinate {
        int row, col;

        Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public static List<Coordinate> findShortestPath(char[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        Coordinate start = null;
        Coordinate end = null;
        Map<Integer, Coordinate> map = new HashMap<>();
        // Find the end coordinates
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 'W') {
                    end = new Coordinate(i, j);
                }
            }
        }

        if (end == null) {
            return null;
        }

        LinkedList<Coordinate> shortestPath = new LinkedList<>();
        int[][] distance = new int[rows][cols];
        Coordinate[][] previous = new Coordinate[rows][cols];
        Queue<Coordinate> queue = new LinkedList<>();
        // Find the nearest 'X' point on the boundary as the start
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                    if (matrix[i][j] == 'X') {
                        start = new Coordinate(i, j);
                        queue.add(start);
                        distance[start.row][start.col] = 1;
                    }
                }
            }
        }
        int count = 0;
        // Perform BFS
        while (!queue.isEmpty()) {
            Coordinate current = queue.poll();
            if (current.row == end.row && current.col == end.col) {
                // Reached the end, reconstruct the path
                Coordinate backtrack = current;
                while (backtrack != null) {
                    shortestPath.add(backtrack);
                    count++;
                    backtrack = previous[backtrack.row][backtrack.col];
                }
                System.out.println(count);
                break;
            }

            for (int[] dir : DIRECTIONS) {
                int newRow = current.row + dir[0];
                int newCol = current.col + dir[1];
                Coordinate neighbor = new Coordinate(newRow, newCol);
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                        && (matrix[newRow][newCol] == 'X' || matrix[newRow][newCol] == 'W') && distance[newRow][newCol] == 0) {
                    distance[newRow][newCol] = 1;
                    previous[newRow][newCol] = current;
                    queue.add(new Coordinate(newRow, newCol));
                }
            }
        }
        return shortestPath;
    }

    public static void printPath(List<Coordinate> path) {
        if (path != null) {
            System.out.println("最短路径坐标为：");
            for (Coordinate coord : path) {
                System.out.println("(" + coord.row + ", " + coord.col + ")");
            }
        } else {
            System.out.println("未找到最短路径");
        }
    }

    public static void main(String[] args) {
        char[][] matrix = {
                "SS             SS  S".toCharArray(),
                "  S S S  S S  S     ".toCharArray(),
                "        S   S  SS S ".toCharArray(),
                "XXXXX         S     ".toCharArray(),
                "  S X   S  S      S ".toCharArray(),
                "  SXXXXXXXXXXXXXX   ".toCharArray(),
                "  S X X         X  S".toCharArray(),
                "    S S        XX S ".toCharArray(),
                "         WXXXXXXX S ".toCharArray(),
                "   S   S          SS".toCharArray(),
                "     S S        S S ".toCharArray(),
                " S   S    SS    S S ".toCharArray(),
                "  SSS    S   S      ".toCharArray(),
                " S   S          SS  ".toCharArray(),
                " S S S  S  S  SS SS ".toCharArray(),
                " S   S         S SS ".toCharArray(),
                " SSSSS     S   S  S ".toCharArray(),
                " SS SS  S      SSSS ".toCharArray(),
                "      S    S   S  SS".toCharArray(),
                "             S      ".toCharArray()
        };

        List<Coordinate> shortestPath = findShortestPath(matrix);
        printPath(shortestPath);
    }
}
